package leetcode.offer0115;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
		int n = nums.length;
		int[] ins = new int[n + 1];// 入度
		List<List<Integer>> nexts = new ArrayList<>();// 后续
		for (int i = 0; i <= n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int i = 0; i < sequences.length; i++) {
			int[] seq = sequences[i];
//			for (int j = 0; j < seq.length; j++) {
//				for (int k = j + 1; k < seq.length; k++) {
//					ins[seq[k]]++;// 入度 + 1
//					nexts.get(seq[j]).add(seq[k]);// 添加后续
//				}
//			}
			for (int j = 1; j < seq.length; j++) {
				ins[seq[j]]++;// 入度 + 1
				nexts.get(seq[j - 1]).add(seq[j]);// 添加后续
			}
		}
		int cur = 0;// 范围是[1,n]
		for (int i = 0; i <= n; i++) {
			if (ins[i] == 0) {
				if (cur == 0) {
					cur = i;
				} else {
					return false;// 多个可能的头，不唯一
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (cur != nums[i]) {
				return false;// 未匹配唯一序列
			}
			// 减少cur的后续入度
			List<Integer> next = nexts.get(cur);
			int nextNum = 0;
			for (int nxt : next) {
				if (--ins[nxt] == 0) {
					if (nextNum == 0) {
						nextNum = nxt;
					} else {
						return false; // 后续不唯一
					}
				}
			}
			cur = nextNum;
		}
		return true;// 顺利检查完毕
	}

	@Override
	public void debug4() {
		H.compare(true,
				this.sequenceReconstruction(H.str2array3("[4,1,5,2,6,3]"), H.str2array1("[[5,2,6,3],[4,1,5,2]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
